package leetcode_400;

import java.util.Arrays;

/**
 *@author 周杨
 *RemoveDuplicateLetters_316 去除字符串中重复的元素 保证原顺序不变且维护字典最先顺序
 *describe: 逐个字母找出。例如要找出第一个字母，首先找到最右边的一个点，使该点右边能够包含全部的字母，则第一个字母必在该点左边（包含该点），
 *寻找方法是从该点向左搜寻，搜寻到一个字母表最靠前的、位置最靠左的字母，则为第一个字母。 AC 94%
 *2018年7月2日 下午8:44:45
 */
public class RemoveDuplicateLetters_316 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}
	public String removeDuplicateLetters(String s) {
        char[] sa = s.toCharArray();
        int[] alphabet = new int[26];
        int count = 0;
        for(int i=0; i<sa.length; i++) {
            if (alphabet[sa[i]-'a']==0) count ++;//记录最终结果有多少位
            alphabet[sa[i]-'a'] ++;//过滤重复的元素
        }
        char[] removed = new char[count];
        int left = 0;
        int right = sa.length;
        int c = 0;
        Arrays.fill(alphabet, 0);
        while (c<count) {//循环结果长度次
            right --;
            if (alphabet[sa[right]-'a']==0) c ++;//只保存该字母第一次出现的最后位置
            alphabet[sa[right]-'a'] ++;
        }
        for(int i=0; i<count; i++) {
            char ch = sa[right];
            int leftmost=right;
            for(int j=right-1; j>=left; j--) {
                if (sa[j] <= ch && alphabet[sa[j]-'a'] != 0) {
                    ch = sa[j];
                    leftmost = j;
                }
            }
            alphabet[ch-'a'] = 0;
            removed[i] = ch;
            left = leftmost + 1;
            while (right<sa.length-1 && alphabet[sa[right]-'a'] != 1) {
                if (alphabet[sa[right]-'a'] > 1) alphabet[sa[right]-'a'] --;
                right ++;
            }
        }
        return new String(removed);
    }
}
